home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / snip0493.zip / ISQRT.C < prev    next >
C/C++ Source or Header  |  1993-04-05  |  2KB  |  92 lines
  1. #include <string.h>
  2.  
  3. #define BITSPERLONG 32
  4.  
  5. #define TOP2BITS(x) ((x & (3 << (BITSPERLONG-2))) >> (BITSPERLONG-2))
  6.  
  7.  
  8. /* usqrt:
  9.     ENTRY x: unsigned long
  10.     EXIT  returns floor(sqrt(x) * pow(2, BITSPERLONG/2))
  11.  
  12.     Since the square root never uses more than half the bits
  13.     of the input, we use the other half of the bits to contain
  14.     extra bits of precision after the binary point.
  15.  
  16.     EXAMPLE
  17.         suppose BITSPERLONG = 32
  18.         then    usqrt(144) = 786432 = 12 * 65536
  19.                 usqrt(32) = 370727 = 5.66 * 65536
  20.  
  21.     NOTES
  22.         (1) change BITSPERLONG to BITSPERLONG/2 if you do not want
  23.             the answer scaled.  Indeed, if you want n bits of
  24.             precision after the binary point, use BITSPERLONG/2+n.
  25.             The code assumes that BITSPERLONG is even.
  26.         (2) This is really better off being written in assembly.
  27.             The line marked below is really a "arithmetic shift left"
  28.             on the double-long value with r in the upper half
  29.             and x in the lower half.  This operation is typically
  30.             expressible in only one or two assembly instructions.
  31.         (3) Unrolling this loop is probably not a bad idea.
  32.  
  33.     ALGORITHM
  34.         The calculations are the base-two analogue of the square
  35.         root algorithm we all learned in grammar school.  Since we're
  36.         in base 2, there is only one nontrivial trial multiplier.
  37.  
  38.         Notice that absolutely no multiplications or divisions are performed.
  39.         This means it'll be fast on a wide range of processors.
  40. */
  41.  
  42. struct int_sqrt {
  43.     unsigned sqrt,
  44.          frac;
  45. };
  46.  
  47. void usqrt(unsigned long x, struct int_sqrt *q)
  48. {
  49.     unsigned long a = 0L;            /* accumulator */
  50.     unsigned long r = 0L;                   /* remainder */
  51.     unsigned long e = 0L;                   /* trial product */
  52.  
  53.     int i;
  54.  
  55.     for (i = 0; i < BITSPERLONG; i++)    /* NOTE 1 */
  56.     {
  57.         r = (r << 2) + TOP2BITS(x); x <<= 2; /* NOTE 2 */
  58.         a <<= 1;
  59.         e = (a << 1) + 1;
  60.         if (r >= e)
  61.         {
  62.             r -= e;
  63.             a++;
  64.         }
  65.     }
  66.     memcpy(q, &a, sizeof(long));
  67. }
  68.  
  69. #ifdef TEST
  70.  
  71. #include <stdio.h>
  72. #include <stdlib.h>
  73.  
  74. main(void)
  75. {
  76.     int i;
  77.     unsigned long l = 0x3fed0169;
  78.     struct int_sqrt q;
  79.  
  80.     for (i = 0; i < 101; ++i)
  81.     {
  82.         usqrt(i, &q);
  83.         printf("sqrt(%3d) = %2d, remainder = %2d\n",
  84.             i, q.sqrt, q. frac);
  85.     }
  86.     usqrt(l, &q);
  87.     printf("\nsqrt(%lX) = %X, remainder = %X\n", l, q.sqrt, q.frac);
  88.       return 0;
  89. }
  90.  
  91. #endif /* TEST */
  92.